package sort;

/**
 * description:
 * author:张腾
 * date:2021-03-04
 */

public class Quick1 {

    public static void main(String[] args) {

        int[] A = new int[]{5,3,5,7,4,6,3,1};
        quickSort(A,0,A.length-1);
        for (int i : A){
            System.out.println(i);
        }
    }

    public static void quickSort(int[] A, int L, int R){
        if (L>=R){
            return;
        }
        int left=L,right=R;
        int pilot = A[left];
        while (left<right){
            while (left<right&&A[right]>=pilot){
                right--;
            }
            if (left<right){
                A[left]=A[right];   //{1,3,5,7,4,6,3,1}  {1,3,5,3,4,6,3,7}
                left++;
            }
            while (left<right&&A[left]<=pilot){
                left++;
            }
            if(left<right){
                A[right]=A[left];   //{1,3,5,7,4,6,3,7}
                right--;
            }
        }
        A[left]=pilot;
        quickSort(A,L,left-1);
        quickSort(A,left+1,R);
    }
}
